package dicTree;

public class MapSumPairs677 {
    DicTree root = new DicTree();

    public MapSumPairs677() {

    }

    public void insert(String key, int val) {
        root.insert(key, val);
    }

    public int sum(String prefix) {
        DicTree rootPre = root.getPre(prefix);
        return sum(rootPre);
    }

    private int sum(DicTree root){
        int result = 0;
        if(root==null){
            return result;
        }
        if(root.isEnd){
            result+=root.value;
        }
        for (int i = 0; i <26; i++) {
            result += sum(root.child[i]);
        }

        return result;
    }



    class DicTree {
        DicTree[] child;
        int value;
        boolean isEnd;

        public DicTree() {
            child = new DicTree[26];
            isEnd = false;
        }

        public void insert(String key, int value) {
            DicTree temp = this;
            for (int i = 0; i < key.length(); i++) {
                char c = key.charAt(i);
                if (temp.child[c - 'a'] == null) {
                    temp.child[c - 'a'] = new DicTree();
                }
                temp = temp.child[c - 'a'];
            }
            temp.isEnd = true;
            temp.value = value;

        }

        public DicTree getPre(String prefix) {
            DicTree temp = this;
            for (int i = 0; i < prefix.length(); i++) {
                char c = prefix.charAt(i);
                if(temp.child[c-'a']==null){
                    return null;
                }
                temp = temp.child[c-'a'];
            }
            return temp;
        }

    }

}
